package com.company.algo.niuke;

public class GetSqrt {
    /**
     * 二分法，注意数值溢出（用除法而非乘法）
     * @param x 目标值
     * @return 开根（向下取值）
     */
    public int sqrt (int x) {
        if (x<2) return x;
        int l=1,r=x,mid,sqrt;
        while (l<=r){   //向下取整，所以要用<=而不是<
            mid = (l+r)/2;
            sqrt = x/mid;
            if (sqrt == mid) return sqrt;
            else if (sqrt > mid) l = mid + 1;
            else r = mid - 1;
        }
        return r;       //向下取整，所以要用r而不是l
    }
}
